#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
#define MaxSize 50
//队列  在表的一端（队尾）插入，另一端删除（队头）  先进先出
//声明队列
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;//队头和队尾指针
}SqQueue;
//队空条件：q->rear==q->front
//队满条件：q->rear==MaxSize-1;
//进队操作：将rear+1，将元素e放在rear位置上
//出队操作：将front+1，取出front位置上的元素
//初始化队列
void InitQueue1(SqQueue *&q)
{
    q=(SqQueue *)malloc(sizeof(SqQueue));
    q->rear=q->front=-1;
}
//销毁队列
void DestroyQueue1(SqQueue *&q)
{
    free(q);
}
//判断是否为空
bool EmptyQueue1(SqQueue *q)
{
    return(q->rear==q->front);
}
//进队列
bool enQueue1(SqQueue *&q,ElemType &e)
{
    if(q->rear==q->front)
        return false;
    q->rear++;//队尾+1
    q->data[q->rear]=e;//在rear位置插入
    return true;
}
//出队列
bool deQueue1(SqQueue *&q,ElemType &e)
{
    if(q->rear==q->front)
        return false;
    q->front++;//队头+1
    e=q->data[q->front];
    return true;
}
//环形队
//初始化队列
void InitQueue(SqQueue *&q)
{
    q=(SqQueue *)malloc(sizeof(SqQueue));
    q->front=q->rear=0;
}
//销毁队列
void DestroyQueue(SqQueue *&q)
{
    free(q);
}
//判断是否为空
bool EmptyQueue(SqQueue *q)
{
    return(q->rear==q->front);
}
//进队列
bool enQueue(SqQueue *&q,ElemType e)
{
    if((q->rear+1)%MaxSize==q->front)
        return false;
    q->rear=(q->rear+1)%MaxSize;
    q->data[q->rear]=e;
    return true;
}
//出队列
bool deQueue(SqQueue *&q,ElemType e)
{
    if(q->front==q->rear)
        return false;
    q->front=(q->front+1)%MaxSize;
    e=q->data[q->front];
    return true;
}
//链队
//在表头删除，表尾插入
//声明链栈
typedef struct qnode
{
    ElemType data;//存放元素
    struct qnode *next;//下一节点的指针
}DataNode;
typedef struct
{
    DataNode *front;//指向首节点
    DataNode *rear;//指向尾节点
}LinkQuNode;
//队空条件：q->rear==Null(q->front==NULL)
//进队操作：新建节点存放e（p指向他），将节点p插入作为尾节点
//出队操作：将首节点的data值取出删除
//初始化队列
void InitQueue2(LinkQuNode *&q)
{
    q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
    q->rear=q->front=NULL;
}
//销毁队列
void DestroyQueue2(LinkQuNode *&q)
{
    DataNode *pre=q->front,*p;
    if(pre!=NULL)
    {
        p=pre->next;
        while(p!=NULL)
        {
            free(pre);
            pre=p;
            p=p->next;
        }
        free(pre);
    }
    free(q);
}
//判断是否为空
bool EmptyQueue2(LinkQuNode *q)
{
    return(q->rear==NULL);
}
//进队列
bool enQueue2(LinkQuNode *&q,ElemType e)
{
    DataNode *p;
    p=(DataNode *)malloc(sizeof(DataNode));
    p->data=e;
    p->next=NULL;
    if(q->rear==NULL)
        q->front=q->rear=p;
    else
    {
        q->rear->next=p;//将队尾指针指向p
        q->rear=p;
    }
    return true;
}
//出队列
bool deQueue2(LinkQuNode *&q,ElemType &e)
{
    DataNode *t;
    if(q->rear==NULL)
        return false;
    t=q->front;
    if(q->front==q->rear)
        q->front=q->rear=NULL;
    else
        q->front=q->front->next;
    e=t->data;
    free(t);
    return true;
}
int main()
{
    ElemType e;
    SqQueue *q;
    printf("环形队列基本运算：\n");
    printf("1.初始化队列：\n");
    InitQueue(q);
    printf("2.依次进队列元素：\n");
    if(!enQueue(q,'1'))
        printf("队满\n");
    if(!enQueue(q,'2'))
        printf("队满\n");
    if(!enQueue(q,'3'))
        printf("队满\n");
    if(!enQueue(q,'4'))
        printf("队满\n");
    if(!enQueue(q,'5'))
        printf("队满\n");
    printf("3.队列为%s\n",(QueueEmpty(q)?"空":"非空"));
    if(deQueue(q,e)==0)
        printf("队空");
    else
        printf("4.出队：%c\n",e);
    printf("5.依次进队：\n");
    if(!enQueue(q,'a'))
        printf("队满\n");
    if(!enQueue(q,'b'))
        printf("队满\n");
    if(!enQueue(q,'c'))
        printf("队满\n");
    if(!enQueue(q,'d'))
        printf("队满\n");
    if(!enQueue(q,'e'))
        printf("队满\n");
    printf("6.出队：");
    while(!QueueEmpty(q))
    {
        deQueue(q,e);
        printf("%c",e);
    }
    printf("\n");
    printf("7.释放队列\n");
    DestroyQueue(q);
    return 1;
}